package array;

public class FindKthIn2SortedArray {

	// assume 2 sorted array as increment
	public static int find(int[] arr1, int[] arr2, int k) {
		assert (k > 0);
		assert (arr1.length > 0 || arr2.length > 0);
		assert (arr1.length + arr2.length >= k);

		if (arr1.length == 0)
			return arr2[k - 1];
		if (arr2.length == 0)
			return arr1[k - 1];

		int result = 0;
		int n = k;
		int half = n / 2;
		int index1 = 0, index2 = 0;
		while (arr1.length - index1 >= half && arr2.length - index2 >= half
				&& n > 1) {
			if (arr1[index1 + half - 1] >= arr2[index2 + half - 1]) {
				index2 = index2 + half;
			} else {
				index1 = index1 + half;
			}
			n = n - half;
			half = n / 2;
		}

		if (arr1.length - index1 == 0) {
			result = arr2[index2 + n - 1];
		} else if (arr2.length - index2 == 0) {
			result = arr1[index1 + n - 1];
		}
		if (arr1.length - index1 >= half && arr2.length - index2 >= half) {
			result = arr1[index1] < arr2[index2] ? arr1[index1] : arr2[index2];
		} else {
			if (arr1.length - index1 >= half) {
				index1 = index1 + (n - (arr2.length - index2));
				index2 = arr2.length;
			} else {
				index2 = index2 + (n - (arr1.length - index1));
				index1 = arr1.length;
			}
			if (arr1[index1 - 1] >= arr2[index2 - 1]) {
				result = arr1[index1 - 1];
			} else {
				result = arr2[index2 - 1];
			}
		}

		return result;
	}

	public static int findIterative(int[] arr1, int[] arr2, int k) {
		assert (k < arr1.length && k < arr2.length);

		int result = 0;
		int index1 = 0, index2 = 0;
		while (k > 1) {
			if (arr1[index1 + k / 2 - 1] < arr2[index2 + k / 2 - 1]) {
				index1 += k / 2;
			} else {
				index2 += k / 2;
			}
			k = k - k / 2;
		}

		result = arr1[index1] < arr2[index2] ? arr1[index1] : arr2[index2];
		return result;
	}

	public static int findRecursive(int[] arr1, int[] arr2, int index1,
			int index2, int k) {
		assert (index1 < arr1.length && index2 < arr2.length && k < arr1.length && k < arr2.length);

		if (1 == k) {
			return arr1[index1] < arr2[index2] ? arr1[index1] : arr2[index2];
		}

		int half = k >> 1;
		if (arr1[index1 + half - 1] < arr2[index2 + half - 1]) {
			index1 = index1 + half;
		} else {
			index2 = index2 + half;
		}
		k = k - half;
		return findRecursive(arr1, arr2, index1, index2, k);
	}

	// assume 2 sorted array as increment
	public static int find1(int[] arr1, int[] arr2, int k) {
		assert (k > 0);
		assert (arr1.length + arr2.length >= k);

		if (arr1.length == 0)
			return arr2[k - 1];
		if (arr2.length == 0)
			return arr1[k - 1];

		int result = 0;
		int n = k;
		int half = n / 2;
		int index1 = 0, index2 = 0;
		while (arr1.length - index1 >= half && arr2.length - index2 >= half) {
			if (arr1[index1 + half] >= arr2[index2 + half]) {
				index2 = index2 + half;
			} else {
				index1 = index1 + half;
			}
			n = n - half;
			half = n / 2;
		}

		int[] arrLong = null, arrShort = null;
		int indexLong = 0, indexShort = 0;
		if (arr1.length - index1 < half) {
			arrShort = arr1;
			arrLong = arr2;
			indexShort = index1;
			indexLong = index2;
		} else {
			arrShort = arr2;
			arrLong = arr1;
			indexShort = index2;
			indexLong = index1;
		}

		indexLong = indexLong + (n - (arrShort.length - indexShort));
		indexShort = arrShort.length - 1;
		if (arrShort[indexShort] >= arrLong[indexLong]) {
			result = arrShort[indexShort];
		} else {
			result = arrLong[indexLong];
		}

		return result;
	}

	public FindKthIn2SortedArray() {
		// TODO Auto-generated constructor stub
	}

	/*
	 * There are two sorted arrays A and B of size m and n respectively.
	 *  Find the median of the two sorted arrays. 
	 *  The overall run time complexity should be O(log (m+n)).
	 */
	public static double findMedianSortedArrays(int A[], int B[]) {
		int m = A.length, n = B.length;

		//if m+n is even, then the median is the average of (m+n)/2 and (m+n)/2 - 1
		//if m+n is odd, then the median is (m+n)/2

		int mid = (m + n) / 2;
		//look for mid in A
		//[start, end]: close region to try. inclusive.
		int start = 0, end = m - 1, midA = 0, midB = 0;
		int median = 0;
		while (start <= end) {
			midA = start + (end - start) / 2;
			midB = mid - midA;
			if (get(B, midB - 1) <= get(A, midA)
					&& get(A, midA) <= get(B, midB)) //index out of bound here.
			{
				//found the median
				median = get(A, midA);
				if ((m + n) % 2 == 0) { //index out of bound here
					int other = Math.max(get(A, midA - 1), get(B, midB - 1));
					return (median + other) * 0.5;
				} else {
					return (double) median;
				}
			} else if (get(A, midA) < get(B, midB - 1)) { //A[i] is smaller than the median
				start = midA + 1;
			} else if (get(A, midA) > get(B, midB)) { //A[i] is bigger than the median
				end = midA - 1;
			}
		}

		//not found the median
		//look for median in B
		return findMedianSortedArrays(B, A);
	}

	public static int get(int[] a, int i) {
		if (i < 0) {
			return Integer.MIN_VALUE;
		} else if (i >= a.length) {
			return Integer.MAX_VALUE;
		} else {
			return a[i];
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//		int[] arr1 = new int[] { 1, 3, 5, 7, 9 };
		//		int[] arr2 = new int[] { 2, 4, 6, 8, 10 };
		//		System.out.printf("expect 5: %d\n", find(arr1, arr2, 5));
		//
		//		arr1 = new int[] { 1, 3, 5, 7, 9 };
		//		arr2 = new int[] { 2, 4, 6, 8, 10, 11, 12, 13 };
		//		System.out.printf("expect 9: %d\n", find(arr1, arr2, 9));
		//		System.out.printf("expect 10: %d\n", find(arr1, arr2, 10));
		//		System.out.printf("expect 11: %d\n", find(arr1, arr2, 11));
		//
		//		for (int i = 1; i <= 5; ++i) {
		//			System.out.printf("expect %d: %d\n", i,
		//					findRecursive(arr1, arr2, 0, 0, i));
		//			System.out.printf("expect %d: %d\n", i,
		//					findIterative(arr1, arr2, i));
		//		}

		int[] A = new int[] { 1, 3, 5, 7, 9, 11 };
		int[] B = new int[] { 13, 15 };
		System.out.printf("midiem %f\n",
				FindKthIn2SortedArray.findMedianSortedArrays(A, B));

	}
}
